Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.


QTRS
  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
ACTIVATE(n__from(X)) → FROM(X)
PI(X) → FROM(0)
SQUARE(X) → TIMES(X, X)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
PI(X) → 2NDSPOS(X, from(0))
PLUS(s(X), Y) → PLUS(X, Y)
TIMES(s(X), Y) → PLUS(Y, times(X, Y))
ACTIVATE(n__cons(X1, X2)) → CONS(X1, X2)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → 2NDSNEG(N, activate(Z))
TIMES(s(X), Y) → TIMES(X, Y)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))
FROM(X) → CONS(X, n__from(s(X)))

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS
  ↳ DependencyPairsProof
QDP
      ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
ACTIVATE(n__from(X)) → FROM(X)
PI(X) → FROM(0)
SQUARE(X) → TIMES(X, X)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
PI(X) → 2NDSPOS(X, from(0))
PLUS(s(X), Y) → PLUS(X, Y)
TIMES(s(X), Y) → PLUS(Y, times(X, Y))
ACTIVATE(n__cons(X1, X2)) → CONS(X1, X2)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → 2NDSNEG(N, activate(Z))
TIMES(s(X), Y) → TIMES(X, Y)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))
FROM(X) → CONS(X, n__from(s(X)))

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
QDP
          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
ACTIVATE(n__from(X)) → FROM(X)
SQUARE(X) → TIMES(X, X)
PI(X) → FROM(0)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Z)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → ACTIVATE(Y)
PLUS(s(X), Y) → PLUS(X, Y)
PI(X) → 2NDSPOS(X, from(0))
TIMES(s(X), Y) → PLUS(Y, times(X, Y))
ACTIVATE(n__cons(X1, X2)) → CONS(X1, X2)
2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → 2NDSNEG(N, activate(Z))
TIMES(s(X), Y) → TIMES(X, Y)
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))
FROM(X) → CONS(X, n__from(s(X)))

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 3 SCCs with 11 less nodes.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
QDP
                ↳ QDPOrderProof
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

PLUS(s(X), Y) → PLUS(X, Y)

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


PLUS(s(X), Y) → PLUS(X, Y)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
PLUS(x1, x2)  =  PLUS(x1)
s(x1)  =  s(x1)

Lexicographic path order with status [19].
Quasi-Precedence:
s1 > PLUS1

Status:
s1: [1]
PLUS1: [1]


The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
                ↳ QDPOrderProof
QDP
                    ↳ PisEmptyProof
              ↳ QDP
              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
QDP
                ↳ QDPOrderProof
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

TIMES(s(X), Y) → TIMES(X, Y)

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


TIMES(s(X), Y) → TIMES(X, Y)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
TIMES(x1, x2)  =  TIMES(x1)
s(x1)  =  s(x1)

Lexicographic path order with status [19].
Quasi-Precedence:
s1 > TIMES1

Status:
TIMES1: [1]
s1: [1]


The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
QDP
                    ↳ PisEmptyProof
              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
QDP
                ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → 2NDSNEG(N, activate(Z))
2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


2NDSPOS(s(N), cons(X, n__cons(Y, Z))) → 2NDSNEG(N, activate(Z))
The remaining pairs can at least be oriented weakly.

2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))
Used ordering: Combined order from the following AFS and order.
2NDSPOS(x1, x2)  =  2NDSPOS(x1)
s(x1)  =  s(x1)
cons(x1, x2)  =  x1
n__cons(x1, x2)  =  n__cons(x1)
2NDSNEG(x1, x2)  =  x1
activate(x1)  =  x1
from(x1)  =  from(x1)
n__from(x1)  =  n__from

Lexicographic path order with status [19].
Quasi-Precedence:
ncons1 > [2NDSPOS1, s1]
nfrom > from1

Status:
from1: [1]
nfrom: []
s1: [1]
2NDSPOS1: [1]
ncons1: [1]


The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
QDP
                    ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

2NDSNEG(s(N), cons(X, n__cons(Y, Z))) → 2NDSPOS(N, activate(Z))

The TRS R consists of the following rules:

from(X) → cons(X, n__from(s(X)))
2ndspos(0, Z) → rnil
2ndspos(s(N), cons(X, n__cons(Y, Z))) → rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z)))
2ndsneg(0, Z) → rnil
2ndsneg(s(N), cons(X, n__cons(Y, Z))) → rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z)))
pi(X) → 2ndspos(X, from(0))
plus(0, Y) → Y
plus(s(X), Y) → s(plus(X, Y))
times(0, Y) → 0
times(s(X), Y) → plus(Y, times(X, Y))
square(X) → times(X, X)
from(X) → n__from(X)
cons(X1, X2) → n__cons(X1, X2)
activate(n__from(X)) → from(X)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 0 SCCs with 1 less node.